package Aleehot100;

import java.lang.reflect.Array;
import java.util.Arrays;

/**
 * ClassName: c060
 * Package: Aleehot100
 * Description: 79. 单词搜索
 *
 * @Author BCXJ
 * @Create 2025/8/10 15:18
 * @Version 1.0
 * @Since 1.0
 */
public class c060 {
    public static void main(String[] args) {
        char[][] arr = {{'A','B','C','E'},
                        {'S','F','C','S'},
                        {'A','D','E','E'}};
        System.out.println(exist(arr, "ABCB"));
    }



    static boolean[][] visited = new boolean[6][6];
    public static boolean exist(char[][] board, String word) {
        // 初始化
        for (int i = 0; i < visited.length; i++) {
            Arrays.fill(visited[i], false);
        }
        char[] charArray = word.toCharArray();
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[i].length; j++) {
                boolean falg = check(board, i, j, charArray, 0);
                if(falg) {
                    return true;
                }
            }
        }
        return false;
    }


    // 上下左右
    static int[][] help = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
    /**
     * 检查元素
     * @param board 源数据
     * @param i 下标 i
     * @param j 下标 j
     * @param charArray  单词
     * @param index 寻找的index
     * @return
     */
    private static boolean check(char[][] board, int i, int j, char[] charArray, int index) {
        if(board[i][j] != charArray[index]) {
            return false;
        } else if(index == charArray.length - 1) {
            return true;
        }
        visited[i][j] = true;
        for (int k = 0; k < 4; k++) {
            int row = i + help[k][0];
            int col = j + help[k][1];
            // 下标需要符合规范
            if((row >= 0 && row < board.length) && (col >= 0 && col < board[0].length) &&  !visited[row][col]) {
                boolean flag = check(board, row, col,  charArray, index + 1);
                if(flag) {
                    return true;
                }
            }
        }
        visited[i][j] = false;
        return false;
    }
}
